package com.mooc.tree.bak.BinTree.exerice;

import java.util.Scanner;

/**
 * @Author zhang.xin
 * @Description: 树的同构（第三章小白专场）
 * @Date 2019/12/25
 */
public class Isomorphic {
    TreeNode[] nodes;
    /**
     * 定义二叉树的节点
     *
     */
    // 二叉树的表示  Q：如何来确定root节点：没有指向的节点
    private class TreeNode{
        private String  data;
        private int left;
        private int right;

        public TreeNode(String data) {
            this.data = data;
            this.left = -1;
            this.right = -1;
        }

        public String getData() {
            return data;
        }

        public void setData(String data) {
            this.data = data;
        }

        public int getLeft() {
            return left;
        }

        public void setLeft(int left) {
            this.left = left;
        }

        public int getRight() {
            return right;
        }

        public void setRight(int right) {
            this.right = right;
        }
    }

    // 构建二叉树
    public TreeNode buildTree(int n) {
        // 存储输入的节点
        nodes = new TreeNode[n];
        // 存储该节点是否有访问
        int[] visited = new int[n];
        Scanner scanner = new Scanner(System.in);
        for (int i = 0 ; i < n ; i ++) {
            String[] lines = scanner.nextLine().split(" ");
            nodes[i] = new TreeNode(lines[0]);
            if (!"-".equals(lines[1])) {
                nodes[i].setLeft(Integer.valueOf(lines[1]));
                visited[nodes[i].left] = 1;
            } else {
                nodes[i].left = -1;
            }
            if (!"-".equals(lines[2])) {
                nodes[i].setRight(Integer.valueOf(lines[2]));
                visited[nodes[i].right] = 1;
            } else {
                nodes[i].right = -1;
            }
        }
        // 判断根节点
        for (int i = 0 ; i < n ; i++) {
            if (visited[i] == 0) {
                return nodes[i];
            }
        }
        return null;
    }
    // 同构判断
    public boolean isOmorphic(TreeNode t1, TreeNode t2) {

        if (t1 == null || t2 == null) {
            return true;
        }
        if ((t1 == null && t2 != null) || (t1 != null && t2 == null)) {
            return false;
        }
        // 判断根节点的值
        if (!(t1.getData()).equals(t2.getData())) {
            return false;
        }
        if (t1.getLeft() != -1 && t2.getLeft() != -1) {
            return isOmorphic(nodes[t1.getLeft()], nodes[t2.getLeft()]);
        }
        if (t1.getRight() != -1 && t2.getRight() != -1) {
            return isOmorphic(nodes[t1.getRight()],nodes[t2.getRight()]);
        }
        if (nodes[t1.getLeft()] != null && nodes[t2.getLeft()] != null
        && (nodes[t1.getLeft()].getData().equals(nodes[t2.getLeft()].getData()))) {
            return isOmorphic(nodes[t1.getLeft()],nodes[t2.getLeft()]) &&
                    isOmorphic(nodes[t1.getRight()], nodes[t2.getRight()]);
        } else {
            return isOmorphic(nodes[t1.getLeft()],nodes[t2.getRight()])
                    && isOmorphic(nodes[t1.getRight()],nodes[t2.getLeft()]);
        }
    }

    // 测试
    public static void main(String[] args) {
        Isomorphic isomorphic = new Isomorphic();
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        TreeNode t1 = isomorphic.buildTree(n);
        int m = scanner.nextInt();
        TreeNode t2 = isomorphic.buildTree(m);
        boolean res = isomorphic.isOmorphic(t1, t2);
        System.out.println(res ? "Yes" : "No");
    }
}
